package org.myy.learn.hot.多维动态规划;

import lombok.extern.slf4j.Slf4j;

/**
 * 力扣5
 */
@Slf4j
public class 最长回文字串 {
    public static String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i=0; i<n; i++){
            dp[i][i] = true;
        }
        int begin = 0;
        int longest = 1;
        for (int subLen=2; subLen<=n; subLen++){
            for (int l=0; l<n; l++){
                int r = l + subLen - 1;
                if (r >= n){continue;}
                if (s.charAt(l) != s.charAt(r)){
                    dp[l][r] = false;
                } else {
                    if (r - l < 3){
                        dp[l][r] = true;
                    } else {
                        dp[l][r] = dp[l+1][r-1];
                    }
                }
//                if (dp[l][r]){
//                    longest = Math.max(longest, r-l);
//                    begin = l;
//                }
//                if (r-l > longest){
//                    longest = r - l;
//                    begin = l;
//                }
                if (dp[l][r] && r-l+1 > longest){  //ToDo 长度是  右-左+1
                    longest = r - l + 1;
                    begin = l;
                }
            }
        }
        return s.substring(begin, begin+longest);
    }

    public static void main(String[] args) {
        String s = "babad";
        String longestPalindrome = longestPalindrome(s);
        log.info("执行结束，longestPalindrome={}", longestPalindrome);
    }
}
